20220324-TIL

오늘 알고리즘 문제는 가장 긴 증가하는 부분 수열 알고리즘을 응용해서 풀어야 하는 문제였다.

• 전깃줄 문제는 전깃줄이 이어진 위치들을 수열로 보는 식으로 접근해서 풀었다. (힘들었음..)
• 처음엔, 가장 많은 전깃줄과 교차하는 전깃줄부터 제거하는 식의 그리디 풀이를 떠올렸었다.
  (모든 전깃줄에 대해, 전깃줄이 나머지 전깃줄들과 교차하는지 확인 -> 최악의 경우에, O(n^3))
• 그러다가 문제집에 적힌 한 줄 설명을 보고 나서야 제대로 된 풀이를 겨우 떠올릴 수 있었다;
  (LIS(Longest Increasing Subsequence) 응용문제 2 라고 적혀있었음 -> 순간 패닉옴;)
• 전체 전깃줄 개수에서 ‘서로 교차하지 않는 전깃줄의 최대 개수’ 를 빼는 식으로 답을 구했다.
  (A에 연결된 부분을 기준으로 전깃줄 정렬 + B에 연결된 부분이 오름차순 = 서로 교차하지 않음)